#include <bits/stdc++.h>
using namespace std;
int m, n, t;
int a[11][31];
int w[31], c[31], p;
int f[201];

int main() {
    cin >> m >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> c[i] >> p;
        a[p][0]++;
        a[p][a[p][0]] = i;
    }

    for (int i = 1; i <= t; i++) {
        for (int v = m; v >= 0; v--) {
            for (int u = 1; u <= a[i][0]; u++) {
                if (w[a[i][u]] > v)
                    continue;
                f[v] = max(f[v], f[v - w[a[i][u]]] + c[a[i][u]]);
            }
        }
    }

    cout <<f[m];
    return 0;
}